Data communications systems comprise data communications equipment and data processing equipment connected together by data transmission links. Information is transmitted over these data transmission links in a serial fashion from one device to another in the form of a stream of information which has an identifiable beginning and end. This serial stream of information contains not only data information which includes the origin and/or destination of the data and information indicating the type of data being conveyed, but also control information which includes information designating the beginning and end of the stream. Before transmission, the data information and the control information are merged together to create one stream of information called the control/data stream.
Bit-oriented data link protocols are a set of predetermined agreements governing the exchange of information. One type of bit oriented protocol is based on a run length code which is used to efficiently merge, and subsequently separate, the control information from the data information before and after transmission on the communications link. The run length code contains a number of ones or zeroes appearing in a certain predetermined sequence. This specified sequence of ones and zeroes provides a way to distinguish between the control information and the data information received.
A symmetrical run length code specifies the maximum run length of both ones and zeroes which can occur during the active state of information transmission. Since a symmetrical run length code guarantees a minimum transition density of ones and zeroes for all data and control streams in the active state, clocking information can be encoded. When idle control information is being transmitted in the idle state, there is no upper bound to the run length of ones or zeroes transmitted. These codes are DC unbalanced.
Symmetrical run length codes are a by-product of the development of the present embodiment. They are identified as a result of the creation of a formal description of ISO 3309 in order to allow the algorithmic manipulation of ISO 3309 constructs. This is a necessary step in developing a parallel implementation of HDLC coding and the resultant family of symmetrical run length codes is mentioned here for completeness, however, they will not be discussed in any greater detail. 0f the general category of run length codes identified, HDLC falls into a second class of run length codes defined here as asymmetrical run length codes.
Asymmetrical run length codes are those that specify either a maximum run length of ones or a maximum run length of zeroes in the active, non-idle state. Since asymmetrical run length codes only guarantee a maximum number of ones in a zero field, or vice versa, they cannot effectively encode clocking information. HDLC limits the number of ones in a zero field. Asymmetrical run length codes are also DC unbalanced.
In HDLC, a flag field is placed at the beginning and the end of the control/data stream to indicate to the receiver when a new stream of data begins and to indicate when the stream of data ends. In HDLC, one control/data stream is called a packet or a frame. Other control symbols are used to abort frames and change line state. The flag field is defined as a unique pattern of ones and zeroes comprising 01111110. The receiver recognizes this pattern as control information and operates accordingly. The frame, however, also contains data information in the form of ones and zeroes whose pattern can be entirely arbitrary. Consequently, it is possible that the flag field pattern, 01111110, could appear at any time during the transmission of data information. If the receiver recognizes this pattern as a frame field instead of the data it represents, the data transmission would be destroyed. To prevent this problem, an operation called "bit stuffing" is used.
The original data stream is altered by placing ("stuffing") a zero bit in the sequence of ones so that the receiver can distinguish data information from control information. This procedure facilitates the subsequent reconstruction of the originally separate control and data streams. The procedure defines an upper bound for the number of ones which appear in a row in data information being transmitted. Above this run length boundary, control information is being transmitted, below or at this boundary data information is being transmitted. This boundary value is set to five in HDLC.
Any segment of the data stream with a run length of ones greater than or equal to this boundary value will be stuffed with a zero bit before being merged with the control stream and consequently passed to the link for transmission. This process keeps all data streams of ones at or below the control/data run length boundary. Control information is encoded into control streams with run length values above the specified run length boundary.
There is a complementary stuffed bit deletion process used on the receive end of the data stream for removing the stuffed bit. The deletion process is invoked after the control/data streams are separated, thereby restoring the original data stream by removing all of the stuffed bits that were added before the transmission of information began.
The processes used to transmit and receive information are as follows:
1. Run length encoding of the control and data streams into the respective link control and data streams. The control stream is directly encoded into run lengths greater than the run length boundary, and the data stream is encoded into run length streams at or below the run length boundary with stuffed zero bits. PA1 2. Merging the link control and data streams together and placing the control/data stream onto the communications link for transmission. PA1 3. Separating the link control stream from the link data stream using the run length boundary as the discriminator. PA1 4. Run length decoding the link control and data streams into the respective control stream and data stream. The link control stream is directly decoded into the original control stream. The link data stream is decoded, through the deletion of the stuffed zero bits, into the original data stream.
In traditional serial implementations of run length coding, all of the encoding and decoding related processes must run at the speed of the communications link. Many communications links currently operate in the one-hundred mega-bit per second to one giga-bit per second range, and consequently, serial coding processes servicing such links must operate in the one-hundred MHz to one GHz range. While current high speed (low density) technologies are available for implementing these high speed processes, they are more costly than high density (low speed) technologies. The advantage of a parallel implementation of run length coding at a particular link speed is that it can be implemented using a lower cost (high density) technology operating at a lower speed than the link. By devising a spatial decomposition of the required coding processes, this parallel processing based implementation is facilitated.